/**
 * 重排链表
 *
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 *
 * 示例 2：
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 *
 * 提示：
 * 链表的长度范围为 [1, 5 * 104]
 * 1 <= node.val <= 1000
 */

/**
 * 这一题我们的每个数都要重新连接后面的一个数,
 * 每个数对应一个数, 这就说明了我们需要找到这
 * 写数的中间数, 然后将后面的链表给倒置, 这样
 * 就可以一个连一个了...
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public void reorderList(ListNode head) {

        ListNode newHead = new ListNode(0);
        newHead.next = head;
        // 定义快慢指针用来寻找中间节点
        ListNode fast = newHead;
        ListNode slow = newHead;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 找到中间的节点 slow, 接下来让倒置后面的链表
        // 画图可以知道, 我们需要倒置的是 slow 后面的节点

        // 倒置
        ListNode cur = slow.next;
        ListNode prev = null;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }

        // 倒置完成后, prev 是在最后一个节点的, 也就是倒置节点的头节点
        // 开始插入
        cur = head;
        while (cur != slow) {
            ListNode tmp1 = cur.next;
            ListNode tmp2 = prev.next;
            cur.next = prev;
            prev.next = tmp1;
            cur = tmp1;
            prev = tmp2;
        }

        // 这里有一个魔鬼细节
        // 为啥会有这个细节呢? 就是因为我们在插入的时候到了 slow 就没有继续插入了
        // 因为继续插入的化, 要是 奇数个数的链表, 那么后面的节点就会指向空, 但是
        // 这个时候要是我们没有动作的话, slow 节点就会不指向空, 会造成 循环链表
        // 所以这个特殊情况我们需要处理
        if (fast == null) {
            slow.next = null;
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        Main test = new Main();
        test.reorderList(node1);
    }
}

class ListNode {
    int val;
    ListNode next;
    public ListNode() {

    }
    public ListNode(int val) {
        this.val = val;
    }
}